/*
  Grupo 2
  
  Luiz Felipe de Souza Mattos 	RA 107822
  
  Debora Maia Silva 	      	RA 101985

*/

#include <stdio.h>
#include <stdlib.h>
#include <malloc.h>
#include <string.h>
#include "pagina.h"

struct _listaVizinho
{
	int indice;
	struct _listaVizinho * prox;
};

typedef struct _listaPrincipal
{
	int caminhomin;
	ListaVizinho * viz;
}ListaPrincipal;

struct _grafo
{
	ListaPrincipal *vetor;
};

struct _listaCorresponde
{
	int indice;
	char site[500];
	struct _listaCorresponde *prox;
};

void InicializaGrafo(Grafo *inicio,int tamanho)
{
	int i;

	for (i = 0;i < tamanho;i++)
	{
		inicio->vetor[i].caminhomin = LONG_MAX;
		inicio->vetor[i].viz = NULL;
	}
}

Grafo * MontaGrafo(int tamanho)
{
	Grafo *inicio;

	inicio = (Grafo *)malloc(sizeof(Grafo));
	inicio->vetor = (ListaPrincipal *)malloc(tamanho * sizeof(ListaPrincipal));

	InicializaGrafo(inicio,tamanho);

	return inicio;
}

/* monta uma lista com o nome do site e seu correspondente indice do parametro - os nomes dos sites sao ordenados pela tabela ascii
   o que facilita na procura do indice pelo site na funcao de achar o menor caminho - lista ordenada do maior para o menor */
void insereCorresponde (ListaCorresponde **lista, char *site, int ind)
{
	ListaCorresponde *aux, *novo;
	
	if(*lista == NULL) /* primeiro a ser inserido, pois a lista esta vazia */
	{
		(*lista) = (ListaCorresponde*)malloc(sizeof(ListaCorresponde));
		strcpy((*lista)->site, site);
		(*lista)->indice = ind;
		(*lista)->prox = NULL;
	}
	
	else /* jah ha elementos na lista, deve-se procurar a posicao correta a inserir */
	{
		aux = *lista;
		
		if( strcmp(aux->site, site) < 0) /* inserir no comeco, pois o a ser inserido eh maior */
		{
			novo = (ListaCorresponde*)malloc(sizeof(ListaCorresponde));
			strcpy(novo->site, site);
			novo->indice = ind;
			novo->prox = aux;
			/* atualiza o inicio da lista */
			*lista = novo;
		}
		
		else /* nao eh maior que o primeiro, procura posicao correta a inserir */
		{
			novo = (ListaCorresponde*)malloc(sizeof(ListaCorresponde));
			strcpy(novo->site, site);
			novo->indice = ind;
			
			while (aux->prox != NULL && (strcmp(aux->prox->site,site) > 0) )
				aux = aux->prox;
			
			/* a posicao correta eh apos aux */
			if(aux->prox == NULL) /* inserir no final */
			{
				aux->prox = novo;
				novo->prox = NULL;
			}
			
			else /* inserir entre dois elementos */
			{
				novo->prox = aux->prox;
				aux->prox = novo;
			}
		}
	}
}

void insereVizinho (ListaVizinho **lista, int numVizinho)
{
	ListaVizinho *aux, *novo;
	
	novo = (ListaVizinho*)malloc(sizeof(ListaVizinho));
	novo->indice = numVizinho;
	novo->prox = NULL;
	
	if(*lista == NULL) /* ainda nao ha vizinhos, primeiro a ser inserido */	
		*lista = novo;
	
	else /* inserir no final */
	{
		aux = *lista;
		
		/* aux apontara para o ultimo e deve-se inserir depois de aux */
		while(aux->prox != NULL)
			aux = aux->prox;
		
		aux->prox = novo;
		
	}
}

/* retorna o inteiro do indice correspondente ao site passado como parametro - recebe a listaCorresponde montada acima como parametro */
int corresponde (ListaCorresponde **lista, char *site)
{
	ListaCorresponde *aux;

	aux = *lista;

	/* anda na lista ate encontrar o site igual ou menor do que o site procurado */
	while (aux != NULL && strcmp(site,aux->site) < 0)
	{
		aux = aux->prox;
	}
	/* caso tenha chegado ao fim da lista ou o site nao esteja na lista retorna
	um flag */
	if (aux == NULL || strcmp(site,aux->site) > 0)
	{
		return -1;
	}
	/* caso o site seja igual, retorna o valor do indice */
	else
		return aux->indice;
}

void liberaListaP (Grafo **lista,int tamanho)
{
	ListaVizinho *auxViz1, *auxViz2;
	int i;
	
	if(*lista == NULL) 
		return;
	else
	{
		for (i = 0;i < tamanho;i++)
		{
		
			if((*lista)->vetor[i].viz != NULL)
			{
				auxViz1 = (*lista)->vetor[i].viz;
				
				while(auxViz1 != NULL)
				{
					auxViz2 = auxViz1;
					auxViz1 = auxViz1->prox;
					/* atualizacao de ponteiro dos vizinhos do registro atual */
					(*lista)->vetor[i].viz = auxViz1;
					free(auxViz2);
				}
			}
		}
		free((*lista)->vetor);
		free(*lista);
		*lista = NULL;
	}
}

void liberaListaC (ListaCorresponde **lista)
{
	ListaCorresponde *aux;

	aux = *lista;

	while (aux != NULL)
	{
		*lista = aux->prox;
		free(aux);
		aux = *lista;
	}
}

/* algoritmo para achar o menor caminho entre um ponto e todos os outros pontos em um grafo */
void dijkstra (Grafo *grafo,int indice1,int tam)
{
	Fila *fila;
	int i,aux;
	ListaVizinho *lista;

	/* monta e inicializa a fila de prioridades */
	fila = (Fila *)MontaFila(tam);
	InsereListaSimples(&fila->lista[0],indice1);
	/* define o tamanho do caminho ate o proprio no como sendo 0 */
	grafo->vetor[indice1].caminhomin = 0;

	/* faz o loop para visitar todos os nos pelo menos uma vez */
	for (i = 0;i < tam;i++)
	{
		/* retira o elemento de maior prioridade da fila */
		aux = RetiraFila(fila,tam);
		/* caso seja o flag de fila vazia */
		if (aux == -1)
		{
			/* sai da funcao pois ja visitou todos os nos possiveis do grafo no maximo
			uma vez */
			LiberaFila(&fila);
			return;
		}
		/* atribui um ponteiro para os vizinhos do no retirado */
		lista = grafo->vetor[aux].viz;
		/* vai adicionando vizinho por vizinho e atualiza o tamanho minimo do caminho caso necessario */
		while (lista != NULL)
		{
			/* atualiza o caminho e insere na fila de prioridades somente se o caminho atual for menor
			do que o ja marcado */
			if (grafo->vetor[lista->indice].caminhomin > grafo->vetor[aux].caminhomin + 1)
			{
				InsereListaSimples(&fila->lista[grafo->vetor[aux].caminhomin + 1],lista->indice);
				grafo->vetor[lista->indice].caminhomin = grafo->vetor[aux].caminhomin + 1;
			}
			lista = lista->prox;
		}
	}
	/* caso saia do loop sem passar pela condicao do final, libera a memoria usada pela fila de 
	prioridades */
	LiberaFila(&fila);
}

int checaIgual(int ori,int des)
{
	if (ori == -1 || des == -1)
		return 0;
	return 1;
}
